package com.zwy.leetcode;

import java.util.*;

public class Array {
    public static void main(String[] args) {

    }

    /**
     * 两数和
     *
     * @param nums
     * @param target
     * @return
     */
    public  int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        int[] a = new int[2];
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                a[0] = map.get(target - nums[i]);
                a[1] = i;
                return a;
            } else {
                map.put(nums[i], i);
            }
        }
        return null;
    }

    /***
     * 买卖股票的最佳时机 II
     * @param prices
     * @return
     */
    public  int maxProfit(int[] prices) {
        int max=0;
        if(prices.length==0||prices.length<=2)return 0;
        for (int i = 0; i <prices.length-1 ; i++) {
            if(prices[i]<prices[i+1]){
                max+=prices[i+1]-prices[i];
            }
        }
        return max;
    }

    /**
     *
     * 旋转数组
     * @param nums
     * @param k
     */
    public void rotate(int nums[], int k) {
        int length = nums.length;

        int []p=new int[length];
        for (int i = 0; i < nums.length; i++) {
            p[i]=nums[i];
        }
        for (int i = 0; i < length; i++) {
            nums[(i + k) % length] = p[i];
        }
    }

    /**
     * 存在重复元素
     * @param nums
     * @return
     */
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            //因为集合set中不能有重复的元素，如果有重复的
            //元素添加，就会添加失败
            if (!set.add(num))
                return true;
        }
        return false;
    }

    /**
     * 只出现一次的数字
     */
    public int singleNumber(int[] nums) {
        Arrays.sort(nums);
        if(nums.length==1)return nums[0];
        if(nums[0]!=nums[1]){
            if(nums[1]==nums[2])return nums[0];
        }

        for(int i=1;i<nums.length-2;i++){
            if(nums[i]!=nums[i-1]&&nums[i]!=nums[i+1])return nums[i];
        }
        if(nums[nums.length-1]!=nums[nums.length-2])return nums[nums.length-1];
        return 0;
    }

    /**
     * 两个数组的交集 II
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersect(int[] nums1, int[] nums2) {
       Arrays.sort(nums1);
       Arrays.sort(nums2);
       List<Integer>list=new ArrayList<Integer>();
       int num1=0;
       int num2=0;
       while(num1<nums1.length&&num2<nums2.length){
           if(nums1[num1]==nums2[num2]){
               list.add(nums1[num1]);
               num1++;
               num2++;
           }
           else if(nums1[num1]<nums2[num2]){
               num1++;
           }
           else if(nums1[num1]>nums2[num2]){
               num2++;
           }
       }
        int[] arr1 = list.stream().mapToInt(Integer::valueOf).toArray();

        return  arr1;
    }

    /**
     * 加1
     * @param digits
     * @return
     */
    public static int[] plusOne(int[] digits) {
        boolean isOver=false;
        int last = digits[digits.length - 1];
        int []p=new int[digits.length+1];
        if(last!=9){
            digits[digits.length-1]+=1;
            return digits;
        }
        for (int i = digits.length-1; i >=0; i--) {
           if(digits[i]==9){
               digits[i]=0;
               isOver=true;
           }
           else{
               digits[i]+=1;
               isOver=false;
               return digits;
           }
        }
        digits[0]=0;
        p[0]=1;
        for (int i = 1; i < p.length; i++) {
            p[i]=digits[i-1];
        }
       return p;
    }

    /**
     * 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int repeat=0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i]==0){
                repeat++;
            }
            else {
                nums[i-repeat]=nums[i];
               if(repeat!=0) nums[i]=0;
            }
        }


    }

    /**
     * 有效的数独
     * @param board
     * @return
     */
    public boolean isValidSudoku(char[][] board) {
        int length = board.length;
        //二维数组line表示的是对应的行中是否有对应的数字，比如line[0][3]
        //表示的是第0行（实际上是第1行，因为数组的下标是从0开始的）是否有数字3
        int line[][] = new int[length][length];
        int column[][] = new int[length][length];
        int cell[][] = new int[length][length];
        for (int i = 0; i < length; ++i)
            for (int j = 0; j < length; ++j) {
                //如果还没有填数字，直接跳过
                if (board[i][j] == '.')
                    continue;
                //num是当前格子的数字
                int num = board[i][j] - '0' - 1;
                //k是第几个单元格，9宫格数独横着和竖着都是3个单元格
                int k = i / 3 * 3 + j / 3;
                //如果当前数字对应的行和列以及单元格，只要一个由数字，说明冲突了，直接返回false。
                //举个例子，如果line[i][num]不等于0，说明第i（i从0开始）行有num这个数字。
                if (line[i][num] != 0 || column[j][num] != 0 || cell[k][num] != 0)
                    return false;
                //表示第i行有num这个数字，第j列有num这个数字，对应的单元格内也有num这个数字
                line[i][num] = column[j][num] = cell[k][num] = 1;
            }
        return true;
    }

    /**
     * 旋转图像
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int temp;
        for (int i = 0;i<matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(j>i) {
                    temp = matrix[i][j];
                    matrix[i][j] = matrix[j][i];
                    matrix[j][i] = temp;
                }
            }
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if(j<matrix.length/2) {
                    temp = matrix[i][matrix.length - j - 1];
                    matrix[i][matrix[0].length - j - 1] = matrix[i][j];
                    matrix[i][j] = temp;
                }
            }
        }

    }


}


